package org.algorithm.二师兄.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;

import java.util.HashSet;

/***
 *  单链表是否是环形
 */
public class 环形链表 {

    public static void main(String[] args) {
        ListNode build = ListNode.build(1, 2, 3, 4, 5);
        ListNode dummy = build;
        while (dummy != null) {
            if (dummy.next == null) {
                dummy.next = build;
                break;
            }
            dummy = dummy.next;
        }
        System.out.println(hasCircle(build));


    }
    // 环形链表的特点是： 链表中的某一个点会是一个小循环了, 只需要判断被循环的这个node是不是在容器里有就行
    private static boolean hasCircle(ListNode build) {
        if (build == null || build.next == null) return false;
        // 1. 根据容器判断， 如果循环了， 那么循环点的下一个node， 如果容器中有， 就代表是循环, 不能根据值来判断， 必须是hashcode
        HashSet<ListNode> hashSet = new HashSet<>(1);
        boolean flag = false;
        while (build != null) {
            ListNode next = build.next;
            if (hashSet.contains(next)) {
                flag = true;
                break;
            }
            hashSet.add(next);
            build = next;
        }

        // 2. 根据双指针判断， 如果某个点进入了循环， 快指针终会与慢指针相逢， 如果不相逢就不是环形
        ListNode slow = build;
        ListNode fast = build.next;

        while (slow != fast) {
            if (slow == null || fast == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        flag = true;
        return flag;
    }


}
